#include <iostream>
#include <vector>
#include <functional>
using namespace std;

#define INT_MIN     (-2147483647 - 1) /* minimum (signed) int value */
#define INT_MAX       2147483647    /* maximum (signed) int value */

template< typename T, typename _Pr >
int maxsum( T* array, int start, int end, _Pr pr )
{
	if( start >= end ) return 0;

	int length = end - start;

	vector<int> leftsum( length );
	leftsum[0] = array[start];
	for( int i = start + 1; i < end; i++ )
	{
		if( pr( leftsum[i - start - 1], 0 ) )
		{
			leftsum[i - start] = array[i];
		}
		else
		{
			leftsum[i - start] = leftsum[i - start - 1] + array[i];
		}
	}

	for( int i = start + 1; i < end; i++ )
	{
		if( pr( leftsum[i - start], leftsum[i - start - 1] ) )
		{
			leftsum[i - start] = leftsum[i - start - 1];
		}
	}
	//for( int i = start; i < end; i++ )
	//{
	//	cout << leftsum[i - start] << " ";
	//}
	//cout << endl;


	vector<int> rightsum( length );
	rightsum[length - 1] = array[end - 1];
	for( int i = end - 2; i >= start; i-- )
	{
		if( pr( rightsum[i - start + 1], 0 ) )
		{
			rightsum[i - start] = array[i];
		}
		else
		{
			rightsum[i - start] = rightsum[i - start + 1] + array[i];
		}
	}

	for( int i = end - 2; i >= start; i-- )
	{
		if( pr( rightsum[i - start], rightsum[i - start + 1] ) )
		{
			rightsum[i - start] = rightsum[i - start + 1];
		}
	}
	//for( int i = start; i < end; i++ )
	//{
	//	cout << rightsum[i - start] << " ";
	//}
	//cout << endl;

	int maxsum = pr( 1, -1 ) ? INT_MAX : INT_MIN;
	for( int i = start + 1; i < end; i++ )
	{
		int sum = leftsum[i - start - 1] + rightsum[i - start];
		if( pr( maxsum, sum ) )
		{
			maxsum = sum;
		}
	}
	return maxsum;
}

int main()
{
	int cases  = 0;
	cin >> cases;
	while( cases-- )
	{
		int count = 0;
		cin >> count;
		if( count == 0 )
		{
			cout << 0 << endl;
			continue;
		}

		int sum = 0;
		vector<int> array( count );
		for( int i = 0; i < count; i++ )
		{
			cin >> array[i];
			sum += array[i];
		}

		int maxplus = maxsum( &array[0], 0, count, std::less<int>() );
		int minplus = maxsum( &array[0], 1, count - 1, std::greater<int>() );
		cout << std::max( maxplus, sum - minplus ) << endl;
	}
	return 0;
}
